//
// Created by francklinson on 2021/7/6.
//
#include <vector>
#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

class Solution {
public:
    /**
     * 每块地的最大高度是根据距离其最近的水源确定的
     * 对每个水源进行bfs
     * @param isWater
     * @return
     */
    vector<vector<int>> highestPeak(vector<vector<int>> &isWater) {
        vector<vector<int>> heightMap(isWater.size(), vector<int>(isWater[0].size(), 1000));
        for (int i = 0; i < isWater.size(); ++i) {
            for (int j = 0; j < isWater[0].size(); ++j) {
                if (isWater[i][j] == 1) {
                    heightMap[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < isWater.size(); ++i) {
            for (int j = 0; j < isWater[0].size(); ++j) {
                if (isWater[i][j] == 1) {
                    bfs(isWater, heightMap, i, j);
                }
            }
        }
        return heightMap;
    }

    /**
     * bfs函数
     * @param isWater
     * @param heightMap
     * @param i
     * @param j
     */
    void bfs(vector<vector<int>> &isWater, vector<vector<int>> &heightMap, int x, int y) {
        const vector<pair<int, int>> movement{{1,  0},
                                              {-1, 0},
                                              {0,  -1},
                                              {0,  1}};
        vector<vector<bool>> seen(isWater.size(), vector<bool>(isWater[0].size(), false));
        queue<pair<int, int>> q;
        q.emplace(x, y);
        int level = -1;
        while (!q.empty()) {
            ++level;
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                auto p = q.front();
                q.pop();
                seen[p.first][p.second] = true;
                heightMap[p.first][p.second] = min(level, heightMap[p.first][p.second]);
                for (int j = 0; j < 4; ++j) {
                    int nextX = p.first + movement[j].first;
                    int nextY = p.second + movement[j].second;
                    if (nextX >= 0 and nextX < isWater.size() and nextY >= 0 and nextY < isWater[0].size() and
                        not seen[nextX][nextY] and heightMap[nextX][nextY] != 0) {
                        q.emplace(nextX, nextY);
                    }
                }
            }
        }
        // 超时
    }
};

class Solution2 // 题解 多源bfs
{
public:
    vector<vector<int>> highestPeak(vector<vector<int>> &isWater) {
        vector<pair<int, int>> movement{{1,  0},
                                        {-1, 0},
                                        {0,  1},
                                        {0,  -1}};
        int R = isWater.size(), C = isWater[0].size();
        vector<vector<int>> res(R, vector<int>(C, 0));
        queue<pair<int, int>> que;
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                if (isWater[r][c] == 1)
                    que.emplace(r, c);              //从水出发,高度为0的点们
        while (!que.empty())                          //多源BFS + 记忆化
        {
            auto p = que.front();
            que.pop();
            int r = p.first;
            int c = p.second;
            for (int i = 0; i < 4; ++i) {
                int nr = r + movement[i].first;
                int nc = c + movement[i].second;
                if (0 <= nr && nr < R && 0 <= nc && nc < C && isWater[nr][nc] == 0) {
                    res[nr][nc] = res[r][c] + 1;
                    isWater[nr][nc] = 1;            //天然的记忆化visited数组  染色法 的思想
                    que.emplace(nr, nc);
                }
            }
        }
        return res;
    }
};


int main() {
    vector<vector<int>> isWater{{0, 0, 1},
                                {1, 0, 0},
                                {0, 0, 0}};

    vector<vector<int>> isWater2{
            {1, 0, 1, 1, 0, 1, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 0, 0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
            {1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
            {0, 0, 1, 0, 1, 0, 0, 0, 1, 0},
            {1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
            {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 0, 1, 1, 0, 1, 1, 0},
            {0, 0, 0, 1, 1, 0, 1, 0, 1, 0},
            {1, 0, 1, 0, 1, 0, 0, 1, 0, 0},
            {0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
            {0, 1, 1, 1, 0, 1, 0, 0, 0, 0},
            {0, 0, 1, 0, 1, 1, 0, 0, 0, 1},
            {0, 0, 1, 1, 1, 1, 1, 0, 0, 0},
            {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
            {1, 1, 1, 0, 0, 0, 0, 0, 0, 0}
    };

    Solution2 sol;
    auto ans = sol.highestPeak(isWater2);
    for (auto &row:ans) {
        for (auto &x:row) {
            cout << x;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}